package com.springboot.java.design.data_structure;

import java.util.Arrays;
import java.util.List;

/**
 * @Author: TongRui乀
 * @Date: 2020-08-19 9:36
 * @description：  测试链表
 */
public class LinkedListTest {


    public static void main(String[] args) {

        LinkedNode head = createLinkedList(Arrays.asList(1, 3, 4, 5, 6, 7, 8));

        printLinkedList(head);

        head = reverseIter(head);

        printLinkedList(head);



    }


    /**
     *  根据给定的列表生成链表并返回头结点
     * @param values
     * @return
     */
    public static LinkedNode createLinkedList(List<Object> values){

        LinkedNode head = new LinkedNode("", values.get(0), null);

        LinkedNode pre = head;

        for (int i = 1; i < values.size(); i++) {

            LinkedNode node = new LinkedNode("", values.get(i), null);

            pre.setNext(node);

            pre = node;
        }

        return head;
    }

    /**
     *  顺序打印链表
     * @param head
     */
    public static void printLinkedList(LinkedNode head){

        if(head == null){
            return;
        }

        LinkedNode next = head;

        do {
            System.out.print(next.getValue() + "   ");
            next = next.getNext();
        }
        while (next != null);

        System.out.println();
    }

    /**
     2 -> 3 -> 4 -> null

     head = 2;
     next = 3;
         ------>
         head = 3;
         next = 4;
         ------>
            head = 4;
            ----------------------4 -> null
            return 4;
         newHead = 4;
         4 -> 3;
         3 -> null;
         --------------------------4 -> 3 -> null
         return 4;
     newHead = 4;
     3 -> 2;
     2 -> null;
     ------------------------------null <- 2 <- 3 <- 4
     */

    /**
     *  递归方式反转链表
     * @param head
     * @return
     */
    public static LinkedNode reverseRecursion(LinkedNode head){

        //  1 -> 2 -> 3 -> 4 -> null
        //  null <- 1 <- 2 <- 3 <- 4

        if(head == null || head.getNext() == null){
            return head;
        }
        // next 节点
        LinkedNode next = head.getNext();
        // 递归调用
        LinkedNode newHead = reverseRecursion(next);
        // next 节点的后继节点设置为当前节点
        next.setNext(head);
        // 将当前节点的后继节点设置为null
        head.setNext(null);

        return newHead;
    }

    /**
     *  遍历反转链表
     * @param head
     * @return
     */
    public static LinkedNode reverseIter(LinkedNode head){

        //  1 -> 2 -> 3 -> 4 -> null
        //  null <- 1 <- 2 <- 3 <- 4

        LinkedNode prev = null;
        LinkedNode curr = head;

        while(curr != null) {
            LinkedNode nxt = curr.getNext();
            curr.setNext(prev); // 翻转箭头
            prev = curr; //三人行
            curr = nxt; //三人行
        }

        return prev;
    }

}
